package com.leetcode.algorithm.y22.m07.w3;

import com.leetcode.algorithm.common.ListNode;

/**
 * 143. 重排链表
 * 
 * https://leetcode.cn/problems/reorder-list/
 * 
 * @author jie.deng
 *
 */
class Question0143Solution01 {

	public void reorderList(ListNode head) {
		if (head == null || head.next == null || head.next.next == null) {
			return;
		}
		// 找中间节点
		ListNode mid = middleNode(head);
		ListNode tmp = mid.next;
		mid.next = null; // 断开前后两部分链表的连接

		// 翻转后半部分链表
		tmp = reverseList(tmp);

		// 合并链表
		mergeTwoLists(head, tmp);
	}

	public void mergeTwoLists(ListNode list1, ListNode list2) {
		if (list2 == null) {
			return;
		}
		ListNode tmp1 = list1.next;
		ListNode tmp2 = list2.next;
		list2.next = tmp1;
		list1.next = list2;
		mergeTwoLists(tmp1, tmp2);
	}

	public ListNode middleNode(ListNode head) {
		// 找中间节点
		ListNode fast = head;
		ListNode slow = head;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}

	public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode listNode = reverseList(head.next);
		head.next.next = head; // 重点
		head.next = null; // 重点
		return listNode;
	}

}